#include<array>
#include<string>
using namespace std;
class Solution {
public:
    string longestPalindrome(string s) {
        array<array<bool,1000>,1000>dp;
        for(auto&e:dp)e.fill(false);
        string ans;
        for(int i=0;i<s.size();i++){
            for(int j=0;j<=i;j++){
                if(s[i]==s[j]){
                    dp[j][i]=j>=i-1?true:dp[j+1][i-1];
                    if(dp[j][i]&&i-j+1>ans.size())
                        ans=s.substr(j,i-j+1);
                }
            }
        }
        return ans;
    }
};